class BSTree {
    private class Node {
	Comparable item;
	Node left;
	Node right;
	public Node(Comparable item) {
	    this.item = item;
	    left = null;
	    right = null;
	}
    }

    private Node root;
    public Comparable find(Comparable x) {
	return find(root, x);
    }
    private Comparable find(Node t, Comparable x) {
	while (t != null)
	    if (x.compareTo(t.item) < 0)
		t = t.left;
	    else if (x.compareTo(t.item) > 0)
		t = t.right;
	    else
		return t.item;
	return null;
    }
    public Comparable findMin() {
	return findMin(root);
    }
    private Comparable findMin(Node t) {
	if (t != null) {
	    while (t.left != null)
		t = t.left;
	    return t.item;
	}
	return null;
    }
    public Comparable findMax() {
	return findMax(root);
    }
    private Comparable findMax(Node t) {
	if (t != null) {
	    while (t.right != null)
		t = t.right;
	    return t.item;
	}
	return null;
    }
    public void insert(Comparable x) {
	root = insert(root, x);
    }
    private Node insert(Node t, Comparable x) {
	if (t == null)
	    t = new Node(x);
	else if (x.compareTo(t.item) < 0)
	    t.left = insert(t.left, x);
	else if (x.compareTo(t.item) > 0)
	    t.right = insert(t.right, x);
	return t;
    }
    public void remove(Comparable x) {
	root = remove(root, x);
    }
    private Node remove(Node t, Comparable x) {
	if (t != null) {
	    if (x.compareTo(t.item) < 0)
		t.left = remove(t.left, x);
	    else if (x.compareTo(t.item) > 0)
		t.right = remove(t.right, x);
	    else if (t.left == null)
		t = t.right;
	    else if (t.right == null)
		t = t.left;
	    else {
		t.item = findMin(t.right);
		t.right = remove(t.right, t.item);
	    }
	}
	return t;
    }

    private void indent(int depth, Node node) {
	for (int i = 0; i < depth; i++)
	    System.out.print("   ");
	System.out.println(node.item);
    }
    private void inorder() {
	inorder(root, 0);
    }
    private void inorder(Node node, int depth) {
	if (node != null) {
	    inorder(node.right, depth+1);
	    indent(depth, node);
	    inorder(node.left, depth+1);
	}
    }

    public static BSTree makeTree(String[] items) {
	BSTree tree = new BSTree();
	for (int i = 0; i < items.length; i++)
	    tree.insert(items[i]);
	return tree;
    }
    public static void testTree(BSTree tree) {
	System.out.println("INORDER");
	System.out.println();
	tree.inorder();
	System.out.println();
	System.out.println("find min: " + tree.findMin());
	System.out.println("find max: " + tree.findMax());
	System.out.println("find E: " + tree.find("E"));
	tree.remove("D");
	System.out.println("INORDER");
	System.out.println();
	tree.inorder();
	System.out.println();
    }
    public static void main(String[] args) {
	String[] rand = {"D", "H", "C", "A", "F", "E", "G", "B"};
	Tree tree = makeTree(rand);
	testTree(tree);

	String[] alpha = {"A", "B", "C", "D", "E", "F", "G", "H"};
	tree = makeTree(alpha);
	testTree(tree);
    }
}